#ifndef HEAP_H
#define HEAP_H
#include<iostream>
int left(int i)  //下标为i的节点的左孩子节点的下标(这里下标从1开始)
{
    return 2*i;
}
int right(int i )  //下标为i的节点的右孩子节点的下标
{
    return 2*i+1;
}
void swap(int &a,int &b)  //交换；
{
    int d=a;
    a=b;
    b=d;
    return;
}
class heap// max_heap;
{
    int size;    //堆大小
    int * p;    //指向数组
public:
    heap(int _size,int *_p): size(_size),p(_p){}
    ~heap(){}
    void max_heapify(int i) //在左右子堆满足maxheap性质的前提下,保证以下标为i的节点为根的堆的最大堆性质
    {
        if(i>=(size/2+1)) return; //此时i节点一定是叶节点或者超出size
        int l=left(i);
        int r=right(i);
        int largest=i;
        if(l<=size&&p[largest-1]<p[l-1])
        {
            largest=l;
        }
        if(r<=size&&p[largest-1]<p[r-1])
        {
            largest=r;
        }
        if(largest!=i)
        {
            swap(p[largest-1],p[i-1]);//交换
            max_heapify(largest); //只需维护被替换根的子堆的maxheap性质
        }
    }
    void buildmaxheap()
    {
        for(int i=size/2;i>=1;i--)   //从最大的非叶节点开始从底向下建立maxheap;
        {
            max_heapify(i);
        }
    }
    void rank()   //不断把最大元依次移动到倒数第一个，倒数第二个....实现排序
    {
        buildmaxheap();
        for(int i=size;i>=2;i--)
        {
            swap(p[i-1],p[0]);
            size--;             //最大元素排好了，size--对剩下size-1元素排序
            max_heapify(1);     //除第一个节点外，其他节点仍满足maxheap性质，仅对第一个节点维护
        }
    }

};

#endif